package W333;

/**
 * @author zxc
 * @date 2023/02/19 11:27
 **/
/**
 * 题目 ：将整数减少到零所需要的最少操作数
 * 题目详述 ：
 * 给你一个正整数 n ，你可以执行下述操作 任意 次：
 * n 加上或减去 2 的某个 幂
 * 返回使 n 等于 0 需要执行的 最少 操作数。
 * 如果 x == 2^i 且其中 i >= 0 ，则数字 x 是 2 的幂。
 *
 * 提示：
 * 1 <= n <= 10^5
 *
 */
public class MinOperations02 {
    /**
     * 思路 ：
     * 即，考虑到 如果 x == 2^i 且其中 i >= 0 ，则数字 x 是 2 的幂。
     * ===>
     *
     * @param n
     * @return
     */
    public int minOperations(int n) {
        int flag = 0;
        while((int)Math.pow(2 , flag) < n){
            flag++;
        }
        // 变量flag，保存了 第一个大于等于n的 2^flag
        // 即，n为 2的幂;
        if((int)Math.pow(2 , flag) == n){
            return 1;
        }
        int maxN = (int)Math.pow(2 , flag) - n;
        int minN = n - (int)Math.pow(2 , flag - 1);
        int max = 0;
        int maxCount1 = 0;
        int maxCount2 = 0;
        int min = 0;
        int minCount1 = 0;
        int minCount2 = 0;
        while(maxN != 0){
            if ((maxN & 1) == 1){
                maxCount1++;
            }
            else {
                maxCount2++;
            }
            maxN = maxN >> 1;
            System.out.println("maxN : " + maxN);
        }
        while(minN != 0){
            if ((minN & 1) == 1){
                minCount1++;
            }
            else {
                minCount2++;
            }
            minN = minN >> 1;
            System.out.println("minN : " + minN);
        }
//        System.out.println(maxCount1 + " " + maxCount2 + " ," + minCount1 + " " + maxCount2);
        max = Math.min(maxCount1 + 1, maxCount2 + 3);
        min = Math.min(minCount1 + 1 , minCount1 + 3);
        return Math.min(max , min);
    }
}
